﻿using System;
using System.Collections.Generic;
using System.Text;

namespace LeetcodeTest._100._30
{
    public class Leetcode23
    {
         public class ListNode
        {
            public int val;
            public ListNode next;
            public ListNode(int x) { val = x; }
        }
        public ListNode MergeKLists(ListNode[] lists)
        {
            if (lists == null || lists.Length == 0)
                return null;
            ListNode newListNode = null, tempNewListNodeNext = null, minNode = null, tempNode = null;
            int minVal = int.MaxValue;
            int minNodeIndex = -1;
            bool isLoop = true;
            bool isFirst = true;
            int notNullCount = 0;
            do
            {
                minVal = int.MaxValue;
                notNullCount = 0;
                for (int i = 0; i < lists.Length; i++)
                {
                    tempNode = lists[i];
                    if (tempNode == null)
                        continue;
                    notNullCount++;
                    if (tempNode.val < minVal)
                    {
                        minNode = tempNode;
                        minVal = tempNode.val;
                        minNodeIndex = i;
                    }
                }

                if (isFirst)
                {
                    if (notNullCount == 0)
                        return null;
                    if (notNullCount == 1)
                        return minNode;
                    newListNode = new ListNode(minNode.val);
                    lists[minNodeIndex] = minNode.next;
                    tempNewListNodeNext = newListNode;
                    isFirst = false;
                    continue;
                }
                if (notNullCount == 1)
                {
                    isLoop = false;
                    tempNewListNodeNext.next = minNode;
                    continue;
                }

                tempNewListNodeNext.next = minNode;
                lists[minNodeIndex] = minNode.next;
                tempNewListNodeNext = tempNewListNodeNext.next;

            } while (isLoop);
            return newListNode;
        }
    }
}
